package com.le.basic.linked.singleDemo;

/**
 * 将单向链表按某值划分成左边小、中间相等、右边大的形式
 * 【题目】 给定一个单向链表的头节点head，节点的值类型是整型，再给定一个 整数pivot。
 * 实现一个调整链表的函数，将链表调整为
 * 左部分都是值小于 pivot 的节点，
 * 中间部分都是值等于pivot的节点，
 * 右部分都是值大于 pivot的节点。
 */
public class QuestionDemo3 {


    public static SingleNode listPartition1(SingleNode head,int p){
        if (head == null) {
            return head;
        }
        SingleNode cur = head;
        int i = 0;
        while (cur != null){
            i++;
            cur = cur.next;
        }
        SingleNode[] node = new SingleNode[i];
        i = 0;
        cur = head;
        while (cur != null && i < node.length){
            node[i++] = cur;
            cur = cur.next;
        }
        arrPartition(node,p);
        for (i = 1; i < node.length; i++) {
            node[i - 1].next = node[i];
        }
        node[i - 1].next = null;
        return node[0];
    }

    private static void arrPartition(SingleNode[] node, int p) {
        int less = -1;
        int more = node.length;
        int index = 0;
        while (index < more){
            if (node[index].data == p){
                index++;
            }else if (node[index].data < p){
                swap(node,++less,index++);
            }else {
                swap(node,index,--more);
            }
        }
    }


    public static void printLink(SingleNode head){
        if (head == null){
            return;
        }
        while (head != null){
            System.out.print(head.data + "-->");
            head = head.next;
        }
    }

    private static void swap(SingleNode[] arr, int a, int b) {
        SingleNode tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

    public static void main(String[] args) {
        singleLinked linked = new singleLinked();
        linked.add(new SingleNode(9));
        linked.add(new SingleNode(0));
        linked.add(new SingleNode(4));
        linked.add(new SingleNode(5));
        linked.add(new SingleNode(1));
        SingleNode head = listPartition1(linked.getHead(), 3);
        printLink(head);

    }
}
